package leetcode.editor.cn;

import java.util.*;

public class P381InsertDeleteGetrandomO1DuplicatesAllowed {
    public static void main(String[] args) {
        RandomizedCollection solution = new P381InsertDeleteGetrandomO1DuplicatesAllowed().new RandomizedCollection();
        solution.insert(4);
        solution.insert(3);
        solution.insert(4);
        solution.insert(2);
        solution.insert(4);
        solution.remove(4);
        solution.remove(3);
        solution.remove(4);
        solution.remove(4);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class RandomizedCollection {

        List<Integer> set;
        int size = 0;
        HashMap<Integer, List<Integer>> indexMap;
        Random random = new Random();

        public RandomizedCollection() {
            set = new LinkedList<>();
            indexMap = new HashMap<>();
        }

        public boolean insert(int val) {
            boolean contain = true;
            if (indexMap.containsKey(val)) {
                contain = false;
            }
            set.add(val);
            List<Integer> orDefault = indexMap.getOrDefault(val, new ArrayList<>());
            orDefault.add(size++);
            indexMap.put(val, orDefault);
            return contain;
        }

        public boolean remove(int val) {
            if (!indexMap.containsKey(val)) {
                return false;
            }
            List<Integer> removeIndexIndex = indexMap.get(val);
            Integer last = set.get(size - 1);
            List<Integer> lastIndexList = indexMap.get(last);
            Integer removeIndex = removeIndexIndex.remove(0);
            set.set(removeIndex, last);
            set.remove(size - 1);
            if (removeIndexIndex.isEmpty()) {
                indexMap.remove(val);
            }
            if (lastIndexList.size() > 0) {
                lastIndexList.remove(lastIndexList.size() - 1);
                lastIndexList.add(removeIndex);
                Collections.sort(lastIndexList);

            }

            size--;
            return true;
        }

        public int getRandom() {
            int i = random.nextInt(size);
            return set.get(i);

        }
    }

/**
 * Your RandomizedCollection object will be instantiated and called as such:
 * RandomizedCollection obj = new RandomizedCollection();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */
//leetcode submit region end(Prohibit modification and deletion)

}